<HTML>
<HEAD>
<!-- This HTML file has been created by texi2html 1.29
     from adt.tnf on 19 December 2010 -->

<TITLE>Abstract data types to be used in specifications - Lists in LIDO Specifications</TITLE>
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#0000EE" VLINK="#551A8B" ALINK="#FF0000" BACKGROUND="gifs/bg.gif">
<TABLE BORDER=0 CELLSPACING=0 CELLPADDING=0" VALIGN=BOTTOM>
<TR VALIGN=BOTTOM>
<TD WIDTH="160" VALIGN=BOTTOM>
<A HREF="http://eli-project.sourceforge.net/">
<IMG SRC="gifs/elilogo.gif" BORDER=0>
</A>&nbsp;
</TD>
<TD WIDTH="25" VALIGN=BOTTOM>
<img src="gifs/empty.gif" WIDTH=25 HEIGHT=25>
</TD>
<TD ALIGN=LEFT WIDTH="475" VALIGN=BOTTOM>
<A HREF="index.html"><IMG SRC="gifs/title.png" BORDER=0></A>
</TD>
<!-- |DELETE FOR SOURCEFORGE LOGO|
<TD>
<a href="http://sourceforge.net/projects/eli-project">
<img
  src="http://sflogo.sourceforge.net/sflogo.php?group_id=70447&amp;type=13"
  width="120" height="30"
  alt="Get Eli: Translator Construction Made Easy at SourceForge.net.
    Fast, secure and Free Open Source software downloads"/>
</a>
</TD>
|DELETE FOR SOURCEFORGE LOGO| -->
</TR>
</TABLE>

<HR size=1 noshade width=785 align=left>
<TABLE BORDER=0 CELLSPACING=2 CELLPADDING=0>
<TR>
<TD VALIGN=TOP WIDTH="160">
<h4>General Information</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="index.html">Eli: Translator Construction Made Easy</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="gindex_1.html#SEC1">Global Index</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="faq_toc.html" >Frequently Asked Questions</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Tutorials</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="EliRefCard_toc.html">Quick Reference Card</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="novice_toc.html">Guide For new Eli Users</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="news_toc.html">Release Notes of Eli</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="nametutorial_toc.html">Tutorial on Name Analysis</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="typetutorial_toc.html">Tutorial on Type Analysis</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Reference Manuals</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ui_toc.html">User Interface</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="pp_toc.html">Eli products and parameters</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lidoref_toc.html">LIDO Reference Manual</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ee.html" >Typical Eli Usage Errors</a> </td></tr>
</table>

<h4>Libraries</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lib_toc.html">Eli library routines</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="modlib_toc.html">Specification Module Library</a></td></tr>
</table>

<h4>Translation Tasks</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lex_toc.html">Lexical analysis specification</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="syntax_toc.html">Syntactic Analysis Manual</a></td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="comptrees_toc.html">Computation in Trees</a></td></tr>
</table>

<h4>Tools</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="lcl_toc.html">LIGA Control Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="show_toc.html">Debugging Information for LIDO</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="gorto_toc.html">Graphical ORder TOol</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="fw_toc.html">FunnelWeb User's Manual</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="ptg_toc.html">Pattern-based Text Generator</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="deftbl_toc.html">Property Definition Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="oil_toc.html">Operator Identification Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="tp_toc.html">Tree Grammar Specification Language</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="clp_toc.html">Command Line Processing</a> </td></tr>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="cola_toc.html">COLA Options Reference Manual</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="idem_toc.html">Generating Unparsing Code</a> </td></tr>
</table>
<p>
<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="mon_toc.html">Monitoring a Processor's Execution</a> </td></tr>
</table>

<h4>Administration</h4>

<table BORDER=0 CELLSPACING=0 CELLPADDING=0>
<tr valign=top><td><img src="gifs/gelbekugel.gif" WIDTH=7 HEIGHT=7 ALT=" o"> </td><td><a href="sysadmin_toc.html">System Administration Guide</a> </td></tr>
</table>

<HR WIDTH="100%">
<A HREF="mailto:eli-project-users@lists.sourceforge.net">
<IMG SRC="gifs/button_mail.gif" BORDER=0 ALIGN="left"></A>
<A HREF="index.html"><IMG SRC="gifs/home.gif" BORDER=0 ALIGN="right"></A>

</TD>
<TD VALIGN=TOP WIDTH="25"><img src="gifs/empty.gif" WIDTH=25 HEIGHT=25></TD>

<TD VALIGN=TOP WIDTH="600">
<H1>Abstract data types to be used in specifications</H1>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="adt_2.html"><IMG SRC="gifs/next.gif" ALT="Next Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="adt_toc.html"><IMG SRC="gifs/up.gif" ALT="Table of Contents" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT="">
<HR size=1 noshade width=600 align=left>
<A NAME="IDX3"></A>
<A NAME="IDX4"></A>
<A NAME="IDX5"></A>
<A NAME="IDX6"></A>
<H1><A NAME="SEC1" HREF="adt_toc.html#SEC1">Lists in LIDO Specifications</A></H1>
<P>
Several language implementation tasks are solved using linear lists
constructed of data elements which are computed at certain tree nodes,
e.g. a the list of parameter types that is part of the type of a function.
Such lists reflect a left-to-right depth-first order of the
corresponding tree nodes. Similarly such lists are decomposed in
other contexts, e.g. to check the types of the arguments of a function
call. This module provides <CODE>.lido</CODE> specifications for such
patterns of linear list usage. The module uses functions of
the linear list module <CODE>List</CODE>. Any assignable C type may be chosen
as type of the list elements.
<P>
This module is instantiated by
<P>
<PRE>
   $/Adt/LidoList.gnrc+instance=TYPE +referto=HDR :inst
</PRE>
where <CODE>TYPE</CODE> is the name of the element type and <CODE>HDR.h</CODE>
is a file that defines the element type, e.g.
<PRE>
   $/Adt/LidoList.gnrc+instance=DefTableKey +referto=deftbl :inst
</PRE>
If the element type is predefined in C the <CODE>referto</CODE> parameter
is omitted, e.g.
<PRE>
   $/Adt/LidoList.gnrc+instance=int :inst
</PRE>
<A NAME="IDX7"></A>
<A NAME="IDX8"></A>
<A NAME="IDX9"></A>
<A NAME="IDX10"></A>
<A NAME="IDX11"></A>
<A NAME="IDX12"></A>
<A NAME="IDX13"></A>
<A NAME="IDX14"></A>
<P>
The module provides two groups of computational roles,
<CODE>TYPEListRoot</CODE>, <CODE>PreTYPEListElem</CODE>, <CODE>PostTYPEListElem</CODE>, 
<CODE>TYPEListElem</CODE>, for construction of a list from attribute values
at tree nodes, and
<CODE>TYPEDeListRoot</CODE>, <CODE>PreTYPEDeListElem</CODE>, <CODE>PostTYPEDeListElem</CODE>,
<CODE>TYPEDeListElem</CODE> for distribution of a list over attributes of tree
nodes. For each of the two cases there is one role that characterizes the
root of the subtree where the list construction or distribution
is applied, and three roles for nodes that are related to list elements.
These three roles affect the order of list elements differently in cases
where the related tree nodes may occur recursively (see below).
<A NAME="IDX15"></A>
<A NAME="IDX16"></A>
<P>
For construction of a list
<CODE>TYPEListRoot</CODE> is associated to a grammar symbol that contains
all occurrences of the roles for its list elements in its
subtree. If <CODE>TYPEListRoot</CODE> occurs recursively in the tree,
its lists are collected separately.
The resulting list of type <CODE>TYPEList</CODE> is obtained by the
attribute <CODE>TYPEListRoot.TYPEList</CODE>.
<P>
A user's computation has to provide the list element values
of type <CODE>TYPE</CODE> by attributes named <CODE>TYPEElem</CODE> at the
symbols which have one of the three element roles.
One of the three roles should be chosen depending on the
desired order of the elements in cases where the list element 
symbol occurs recursively in the tree:
<P>
If the role <CODE>PreTYPEListElem</CODE> is used the elements are taken 
in pre-order;
i.e. the attribute value of a node occurs in the list prior to those
of nodes in its subtrees.
<P>
If the role <CODE>PostTYPEListElem</CODE> is used the elements are taken 
in post-order;
i.e. the attribute value of a node occurs in the list after those
of nodes in its subtrees.
<P>
If the role <CODE>TYPEListElem</CODE> is used no elements are taken 
from subtrees of an element node.
<A NAME="IDX17"></A>
<P>
There are situations where not all tree nodes that have the role
<CODE>TYPEListElem</CODE> shall contribute an element to the list.
A condition attribute <CODE>TYPEListElem.TYPETakeIt</CODE> of type
<CODE>int</CODE> can be computed such that it is false (<CODE>0</CODE>)
if this tree node shall not contribute to the list.
The value of the attribute <CODE>TYPEListElem.TYPEElem</CODE>
is irrelevant in that case.
If the condition attribute <CODE>TYPEListElem.TYPETakeIt</CODE>
is true the value of the attribute <CODE>TYPEListElem.TYPEElem</CODE>
is taken as an element of the list.
A default computation sets <CODE>TakeIt</CODE> to true (<CODE>1</CODE>).
It becomes effective if it is not overridden as described above.
<A NAME="IDX18"></A>
<A NAME="IDX19"></A>
<A NAME="IDX20"></A>
<P>
<CODE>TYPEFilterListElem</CODE> is outdated. Its task should be achieved
using the attribute <CODE>TYPETakeIt</CODE>. 
<CODE>TYPEFilterListElem</CODE> may be used instead of <CODE>TYPEListElem</CODE>.
Then the value <CODE>TYPEFilterListElem.TYPEElem</CODE> will only be inserted into
the list if a call of the function <CODE>TYPEFilter</CODE> yields non-null
when given <CODE>TYPEFilterListElem.TYPEElem</CODE> as argument.
The function <CODE>TYPEFilter</CODE> has to be defined if the role
<CODE>TYPEFilterListElem</CODE> is used.
<A NAME="IDX21"></A>
<P>
For decomposition of a list
<CODE>TYPEDeListRoot</CODE> is associated to a grammar symbol,
and a computation has to be provided such that the attribute
<CODE>TYPEDeListRoot.TYPEList</CODE> gets a list value.
That list value is decomposed such that each 
occurrence of grammar symbols having one of the element roles
for decomposition (see below)
get a list element value. The list element values are obtained
by attributes named <CODE>TYPEElem</CODE>.
If the list is shorter than the number of the element nodes
in the subtree the attributes of the remaining nodes
get the value <CODE>NoTYPE</CODE>.
<CODE>TYPEDeListRoot.TYPEListTail</CODE> is the
list of remaining elements which are not associated to 
element nodes in the subtree, if any.
<P>
One of the three element roles for list decomposition should be 
chosen depending on the
desired order of the elements in cases where the list element 
symbol occurs recursively in the tree:
<P>
If the role <CODE>PreTYPEDeListElem</CODE> is used the list elements
are associated to <CODE>TYPEElem</CODE> attributes of nodes in pre-order,
i.e. the attribute of a node gets an element of the list which
occurs before those elements in the list that are
distributed at the subtrees of the node.
<P>
If the role <CODE>PostTYPEDeListElem</CODE> is used the list elements
are associated to <CODE>TYPEElem</CODE> attributes of nodes in post-order,
i.e. the attribute of a node gets an element of the list which
occurs after those elements in the list that are
distributed at the subtrees of the node.
<P>
If the role <CODE>TYPEDeListElem</CODE> is used no elements are distributed
to subtrees of an element node.
<A NAME="IDX22"></A>
<P>
A condition attribute <CODE>TYPETakeIt</CODE> of type
<CODE>int</CODE> is computed to true (<CODE>1</CODE>) by default. 
It determines whether an
element of the list is taken at this node. That computation may be 
overridden by a nontrivial computation if such a condition
is desired.
<P>
If list decomposition is used the name <CODE>NoTYPE</CODE> has to be 
defined suitably in a user's specification,
e.g. in <CODE>HDR.h</CODE>. 
<P>
Both <CODE>TYPEListRoot</CODE> and <CODE>TYPEDeListRoot</CODE> may be
recursively nested without affecting each other.
<P>
An example for the use of this module in type analysis is given in
(see  `Function Types' of <CITE>Type analysis tasks</CITE>): 
In the context of a function declaration
the list of parameter types is composed and associated as a
property of the function type. In the context of a function
call that property is accessed, the list is decomposed, and
its elements - the formal parameter types - are compared with
the types of the arguments.
<P>
<HR size=1 noshade width=600 align=left>
<P>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="adt_2.html"><IMG SRC="gifs/next.gif" ALT="Next Chapter" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT=""><A HREF="adt_toc.html"><IMG SRC="gifs/up.gif" ALT="Table of Contents" BORDER="0"></A>
<IMG SRC="gifs/empty.gif" WIDTH=25 HEIGHT=25 ALT="">
<HR size=1 noshade width=600 align=left>
</TD>
</TR>
</TABLE>

</BODY></HTML>
